import java.util.HashMap;
import java.util.Map;

/**
 * 大家都知道斐波那契数列，现在要求输入一个正整数 n,
 * 请你输出斐波那契数列的第 n(n <= 39) 项。
 *    0 1 1 2 3 5 8 13 21 ...
 *
 * Date: 2022-09-29
 * Time: 22:15
 */



public class Algorithm {

    // 普通递归
    public static long Fibonacci(long n) {
        // // 迭代 时间复杂度: O(n)
        // if(n == 0) { return 0; }
        // if(n == 1 || n == 2) { return 1;}

        // int f1 = 1;
        // int f2 = 1;
        // int f3 = 2;

        // for(int i = 3; i <= n; ++i) {
        //     f3 = f2 + f1;
        //     f1 = f2;
        //     f2 = f3;
        // }
        // return f3;

        // 普通的递归实现
        if(n == 0) { return 0; }

        if(n <= 2) { return 1; }

        return Fibonacci(n-1) + Fibonacci(n-2);

    }

    // 结合 map的递归: 防止过多的多余计算.
    private static final Map<Long, Long> filter = new HashMap<>(); //filter过滤的意思
    // 这个map的key值为斐波那契的项数, val值为其对应的值.
    public static long Fibonacci2(long n) {
        if(n <= 1) { return n; }
        if(n == 2) { return 1; }

        // 先计算 n-2 的递归 再计算 n-1 的递归会更好一些~~

        long pPre; // 表示 n-2
        if(filter.containsKey(n-2)) {
            // 在map中找到了n-1 说明已经进行过了 n-2 的递归
            pPre = filter.get(n-2);
        } else {
            // 没找到 将第n-1 和 其对应的结果放入 map中.
            pPre = Fibonacci2(n-2);
            filter.put(n-2,pPre);
        }

        long pre; // 表示 n-1
        if(filter.containsKey(n-1)) {
            // 在map中找到了n-1 说明已经进行过了 n-1 的递归
            pre = filter.get(n-1);
        } else {
            // 没找到 将第n-1 和 其对应的结果放入 map中.
            pre = Fibonacci2(n-1);
            filter.put(n-1,pre);
        }

        return pre + pPre;
    }

    public static void main(String[] args) {
        long k = 47;

        long startTime = System.currentTimeMillis();
        System.out.println(Fibonacci(k));
        long endTime = System.currentTimeMillis();
        System.out.print("普通递归求斐波那契数列第" + k + "项所用时间: ");
        System.out.println(endTime - startTime + "ms");

        long startTime2 = System.currentTimeMillis();
        System.out.println(Fibonacci2(k));
        long endTime2 = System.currentTimeMillis();
        System.out.print("结合map的递归求斐波那契数列第" + k + "项所用时间: ");
        System.out.println(endTime2 - startTime2 + "ms");

    }
}
